#include <vector>
#include <string>
#include <unordered_map>
#include <algorithm>

using namespace std;

class UnionFind
{
public:
    vector<int> parent;

    UnionFind(int n)
    {
        parent.resize(n);
        for(int i = 0; i < n; ++i)
        {
            parent[i] = i;
        }
    }

    void unionSet(int index1, int index2)
    {
        parent[find(index2)] = find(index1);
    }

    int find(int index)
    {
        if(index != parent[index])
        {
            parent[index] = find(parent[index]);
        }
        return parent[index];
    }
};

// 721. 账户合并
class Solution1
{
public:
    vector<vector<string>> accountsMerge(vector<vector<string>>& accounts) 
    {
        unordered_map<string, int> emailToIndex;
        unordered_map<string, string> emailToName;
        int emailCount = 0; // email 的数量作为并查集的大小
        for(auto& account : accounts)
        {
            string& name = account[0];
            int n = account.size();
            for(int i = 1; i < n; ++i)
            {
                string& email = account[i];
                // 建立映射
                if(!emailToIndex.count(email))
                {
                    // 两条不同记录拥有相同的 email，则说明这两条记录的用户是同一
                    // 个人，通过 emailCount 来关联并合并这两条记录的其他 email
                    emailToIndex[email] = emailCount++;
                    emailToName[email] = name;
                }
            }
        }

        // 用 emailId 来表示不同的集合，然后再进行合并
        UnionFind ufs(emailCount);
        for(auto& account : accounts)
        {
            string& firstEmail = account[1];
            int firstIndex = emailToIndex[firstEmail];
            int n = account.size();
            for(int i = 2; i < n; ++i)
            {
                string& nextEmail = account[i];
                int nextIndex = emailToIndex[nextEmail];
                // 将同一个用户的 email 加入到同一个集合中
                ufs.unionSet(firstIndex, nextIndex);
            }
        }

        // key 是一个集合的父节点的 emailId，也就是父节点的 emailId
        // 相同，则说明这些 email 都是同一个用户的
        unordered_map<int, vector<string>> indexToEmails; 
        for(auto& [email, _] : emailToIndex)
        {
            // 找出父节点的 emailId
            int index = ufs.find(emailToIndex[email]);
            // 获取之前属于该 emailId 集合中所有的 email
            vector<string>& account = indexToEmails[index];
            // 将新的 email 添加到 emailId 集合中
            account.emplace_back(email);
            // 将更新后的 emailId 集合记录起来
            indexToEmails[index] = account;
        }

        vector<vector<string>> ret;
        for(auto& [_, emails] : indexToEmails)
        {
            // 同一个用户的 email 要按字典序排序
            sort(emails.begin(), emails.end());
            // 获取这些 email 所属的用户
            string& name = emailToName[emails[0]];
            vector<string> account;
            account.emplace_back(name);
            for(auto& email : emails)
            {
                account.emplace_back(email);
            }
            ret.emplace_back(account);
        }

        return ret;
    }
};

// 785. 判断二分图
class Solution2
{
private:
    static constexpr int UNCOLORED = 0;
    static constexpr int RED = 1;
    static constexpr int GREEN = 2;

    vector<int> color; // 标记节点都涂了什么颜色
    bool vaild; // 表示是否可以被划分成二分图

    void DFS(const vector<vector<int>>& graph, int curNode, int curColor)
    {
        color[curNode] = curColor; // 给当前节点涂色
        int nextColor = (curColor == RED ? GREEN : RED);
        for(auto neighbor : graph[curNode])
        {
            if(color[neighbor] == UNCOLORED)
            {
                DFS(graph, neighbor, nextColor);
                // 不能被划分成二分图，则立即返回
                if(!vaild) return;
            }
            else if(color[neighbor] != nextColor)
            {
                // 标记不能被划分成二分图，并立即返回
                vaild = false;
                return;
            }
        }
    }

public:
    bool isBipartite(vector<vector<int>>& graph) 
    {
        int n = graph.size();
        vaild = true;
        color.resize(n, UNCOLORED);
        for(int i = 0; i < n && vaild; ++i)
        {
            // 遇到一个未涂色的节点，默认给它涂上红色
            if(color[i] == UNCOLORED) DFS(graph, i, RED);
        }
        return vaild;
    }
};